iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
自我挑戰組

Leetcode刷題筆記系列 第 27

[Day 27] Leetcode 207. Course Schedule (C++)

  • 分享至 

  • xImage
  •  

前言

今天選擇的是TOP 100 LIKED的另外一題~207. Course Schedule,牽涉到一個經典的演算法,一起來看看吧!

想法

這題的題目是給了一堆課的先修要求,然後要檢查是否可以在不違反這些先修課要求的條件下完成它。
而這題首要之務就是先轉換題目成比較可以使用的格式,因此我想:先把修課要求存成map,如下:

// for every course, record the course that would study after that
unordered_map<int, vector<int>> preCourseRev;
for(int i=0;i<prerequisites.size();++i){
    preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
}

然後我就卡住了,一開始的判斷想說這題應該是要看有沒有出現死結,所以就針對每一堂課,去追溯他的先修課,DFS去追每一堂課的前面,直到出現重複的。然後就TLE了XD:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // record the prerequisites first
        map<int, vector<int>> preCourse;
        for(int i=0;i<prerequisites.size();++i){
            preCourse[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        // keep record to required courses
        vector<int> seen(numCourses, 0);
        //int checked[numCourses]={0};
        
        
        // check for every courses
        for(int i=0;i<numCourses;++i){
            seen={0};

            // if not checked yet
            //if(checked[i]==0){
                // trace to see if prerequisites conflict
                //seen[i] = 1;
                //for(int j : preCourse[i]){
            if(checkForCourse(i, seen, preCourse)==false){
                return false;
            }
       // }
            //}
        }
        return true;
    }
    bool checkForCourse(int i, vector<int> &seen,map<int, vector<int>> &preCourse){
        if(seen[i]==1){
            return false;
        }
                

        else{
            seen[i]=1;
            for(int j: preCourse[i]){
                if(checkForCourse(j, seen, preCourse)==false){
                        return false;
                }
            }
            seen[i]=0;
            //checked[i]==1;
            return true;
        }
    }
};

檢討結果是我這樣重複得計算搞得太多,等於每堂課分岔再分岔去它前面修過的課,針對每次修過的課又檢查好幾次,其實每次應該檢查自己就好了。
不過其實這題應用的是這個重點─Topological sort演算法,可以參考這邊提供的說明Topological Ordering
整個演算法的重點就是:

  • 前置作業─課堂計算
  1. 同前面所說,先轉換成每一堂課的map
  2. 計算每堂課有幾門先修課
  3. 計算有幾堂課沒有先修課,那就是接下來可以作為第一堂課的課,我們把它存在一個queue裡
  • 遍歷每一堂課
    現在我們要來排序了,我們總共要修n堂課,所以會遍歷n堂,而起點就應該是沒有先修課的一堂課
  1. 如果還沒遍歷完n堂課,但卻每堂課都有先修課,代表其中有cycle,找不到一個起點,所以可以直接return false
  2. 如果有沒有先修課的課,我們就把其中一堂課從QUEUE裡取出來修完它
  3. 修完它我們就不管它了,直接把它需要的課設為-1個
  4. 針對其他堂課,我們檢查如果先修課包含剛剛那門修掉的課,那它們的先修課數目就-1,如果變成0了,就可以加到前面那個queue裡
  5. 持續4~7的步驟,直到違反4而回傳false或順利遍歷完回傳true
    寫出來的解法如下,可以accepted:
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        for(int i=0;i<prerequisites.size();++i){
            ++degrees[prerequisites[i][1]];
        }
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
        }
        return true;
    }      
};

這是按照我對此演算法理解寫出來的版本,後來優化前面兩件事可以一起做+可以提早結束如下:
優化的是把前面1.2的計算寫在同一個for裡完成,並在最後加一個判斷如果queue的數量=剩下課程的數量,代表大家都沒先修課了,可以隨便按照順序也沒關係,因此可以直接回傳true。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
            ++degrees[prerequisites[i][1]];
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
            // if there are no links now could be stop early
            if(q.size()==numCourses-i){
                return true;
            }
        }
        return true;
    }      
};

結語

說好的sum系列一直沒有繼續XD
倒數第4天了,繼續來完成它們吧!


上一篇
[Day 26] Leetcode 283. Move Zeroes (C++)
下一篇
[Day 28] Leetcode 78. Subsets (C++)
系列文
Leetcode刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言